package leetcode16;

public class test89 {
    /**
     * 5. 最长回文子串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if(s.length() < 2){
            return s;
        }
        int len = s.length();
        int maxlen = 1;
        int begin = 0;
        boolean[][] dp = new boolean[len][len];

        for(int i = 0;i < len;i++){
            dp[i][i] = true;
        }

        char[] c = s.toCharArray();
        for(int j = 1;j < len;j++){
            for(int i = 0;i < j;i++){
                if(c[i] != c[j]){
                    dp[i][j] = false;
                }else{
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if(dp[i][j] && j - i + 1 > maxlen){
                    maxlen = j - i + 1;
                    begin = i;
                }
            }

        }
        return s.substring(begin,begin + maxlen);
    }
}
